package top.k.frequent;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Time 2020/1/4
 * @author 王光浩
 * @Need 给出一个整型数组，找出其中前k个出现频率最高的数字。
 * @Thinking 使用HashMap+List集合。
 *           首先将数组中的元素整合进入HashMap中第二步为创建一个长度等于nums长度的整型List数组，然后遍历
 *           HashMap，将value作为List的下标，获取List对象，然后将key加入该对象中，第三步为遍历List数组
 *           从后向前遍历，获取值不为null的前k个元素保存在result集中。
 *           时间复杂度O（n+n+n），空间复杂度O（n+n+k），n为数组长度，k为k的大小。
 *           很棒的一个方法。
 */
public class OtherMethod {
    public List<Integer> topKFrequent(int[] nums, int k) {
    	Map<Integer,Integer> deal=new HashMap<Integer,Integer>();
    	List<Integer>[] bucket=new ArrayList[nums.length+1];             
    	List<Integer> result=new ArrayList<Integer>();
    	//将数组中的数据进行整合
    	for(int i:nums) {
    		deal.put(i, deal.getOrDefault(i, 0)+1);
    	}
    	//将数据存入bucket中
    	for(Map.Entry<Integer, Integer> entry : deal.entrySet()) {
    		if(bucket[entry.getValue()]==null)
    			bucket[entry.getValue()]=new ArrayList<Integer>();
    		bucket[entry.getValue()].add(entry.getKey());
    	}
    	//从后向前在bucket中取出k个值
    	for(int i=bucket.length-1;i>=0 && result.size()<k;i--) {
    		if(bucket[i]!=null) {
    			result.addAll(bucket[i]);
    		}
    	}
    	return result;
    }
}
